package 剑指offer;

import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:33:21 
* @Description：
* 
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
*/


/*
 * 斐波那契数列的标准公式为：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
 */
public class $7斐波那契数列 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		System.out.println(Fibonacci(n));
	}
	
	//递归方法
//	时间复杂度：O(2^n)
//	空间复杂度：O(1)
	
	 public static int Fibonacci(int n) {                          //递归一定要有出口 
		 if(n<=1)                                                            //小心堆栈溢出问题 stackOverflow
			 return n; 
		 return Fibonacci(n-1)+Fibonacci(n-2);
	 }
	 
	 
	 //优化递归，因为递归会重复计算大量的相同数据，可以把子结果用数组保存起来
	 
	 /*
	  * 时间复杂度：O(n)
		空间复杂度：O(n)            借用temp临时数组保存结果，解空间换时间
	  */
	 public static int Fib1(int n) {
		 int [] temp=new int [40];                //这里的数组长度取决于n的取值范围，这里n<39
		 temp[0]=0;
		 temp[1]=1;                                      //简单的来说，就是将找出开始的规律，即temp[0]=1
		 for (int i = 2; i <n; i++) {					//temp[1]=1;由公式知道temp[i]=temp[i-1]+temp[i-2];
			temp[i]=temp[i-1]+temp[i-2];    //分别保存了temp[2]=temp[1]+temp[0],这一步的操作直接可以从上一步的结果中取出使用
		}
		 return temp[n];
	 }

	 
	 //优化存储 ，从上面就可以知道其实这一次的结果只需要关联到上一次和上上一次，总共
	 //是相连的最近两个数，只需要保存这两个就可以了，不需要全部保存先来，节省空间
	 
	 /*
	  * sum 存储第 n 项的值
		one 存储第 n-1 项的值
		two 存储第 n-2 项的值
	  */
/*
 * 	 时间复杂度：O(n)
	空间复杂度：O(1)
 */
	 
	 
	 public static int fib2(int n) {
		 if (n==0) {
			return 0;
		}else if (n==1) {
			return 1;
		}
		 
		 int sum=0;                               //     1   	1		2		3		5		8
		 int one=1;                                //    two  one                
		 int two=0;                               //             two   one
		 
		 for (int i = 2; i <=n; i++) {
			sum=one+two;                              //计算sum最终的结果值
			two=one;										  //因为最后的值只与前两项相关，所以在循环当中不断的改变这两个辅助值
			one=sum;                                     // two 变为one,one变为sum,每一个都往后移动一项
		}
		 return sum;
	 }
	 
	 
	 

	//持续优化， sum 只在每次计算第 n 项的时候用一下，其实还可以利用 sum 存储第 n-1 项，
	 //例如当计算完 f(5) 时 sum 存储的是 f(5) 的值，当需要计算 f(6) 时，f(6) = f(5) + f(4)，sum 存储的 f(5)，f(4) 存储在 one 中，由 f(5)-f(3) 得到
	 
	 /*
	  * 时间复杂度：O(n)
		空间复杂度：O(1)
	  */
	 public static int fib3(int n) {
		 if (n==0) {
			return 0;
		}else if (n==1 ) {
			return 1;
		}
		 
		 int sum=1;                                               //很巧妙的，找出  n与n-1 ，n+1项之间的关系
		 int one=0;
		 for (int i = 2;i<=n; i++) {
			sum=sum+one;
			one=sum-one;
		}
		 return sum;
	 }
}
